1. Technical Field
The present invention is directed to an improved computing system. More specifically, the present invention is directed to an improved method and system for dynamically determining configuration values for improved performance in an autonomic computing system based on geometrical simplex transformations in the underlying multi-dimensional parameter space.
2. Description of Related Art
The success of service-oriented Information Technology, such as Autonomic Computing, On-demand eBusiness and eCommerce, depends critically on the ability to provide information, goods, and services in a fast, efficient and cost-effective fashion. Unfortunately, the increasing complexity of the computing systems necessary to provide these services is rapidly outstripping human ability for system operation. This is especially true when it comes to optimization of system parameters for these complex computing systems.
The fundamental difficulties in real-time optimization of system parameters in large complex systems arise from a number of sources. In many situations, a good model of the system and the way the system interacts with the world is not available (or may be too expensive to obtain). The lack of such a system model prohibits the use of sophisticated analytical and simulation tools for online (i.e., real-time) or offline optimization of the system parameters.
The problem is further compounded by the fact that there may be multiple parameters that have to be optimized simultaneously to improve system performance. Since a model of the system is not accessible, there is little understanding of the relative importance of the different system parameters (in terms of how each parameter effects the system's performance) and of the potential nonlinear interactions between the different parameters (in terms of their combined effect on the system's performance).
In situations where a model of the system is not at hand, one widely adopted technique is to sparsely sample the multidimensional parameter space (say, in a regular grid-like manner) and adopt the parameter setting that provides the best performance among the sampled points. Unfortunately, due to the curse of dimensionality, the number of necessary samples increases exponentially with the number of parameters to be optimized. Thus, even for a small set of parameters, the cost and time needed for a reasonable sampling of the multidimensional parameter space may be too prohibitive. Moreover, for these reasons, such sampling and optimization cannot be performed dynamically in real-time.
In addition, a system's behavior may be stochastic in nature and/or it may operate in a noisy and dynamic environment, such that similar system configuration parameters may result in very different overall performance measures or utility values. Thus, the ability to use historical data to infer a system model is seriously jeopardized, especially in a dynamic environment where demand or the load that is placed on the system is changing continuously over time.
In spite of all the above difficulties, it is the administrator's job to (re)configure the system parameters and improve the system's performance (as measured by a given metric) while the system is in operation. This calls for new methods and apparatus for dynamic, online, multi-parameter optimization that can automatically and quickly configure and tune system parameters without human intervention. The focus of such methods is not necessarily on determining the provably optimal parameter settings, but on finding reasonably good solutions reasonably quickly. Such methods are likely to play a fundamental role in Autonomic Computing, On-demand eBusiness and eCommerce system where there is a significant benefit in providing superior performance in unpredictable complex environments.
Known mechanisms used to perform off-line multi-parameter optimization include the Direct Search methods, and its variants (e.g., simplex algorithm and pattern search). The popularity of such class of methods exist because (i) they tend to work well in practice, (ii) they can often avoid pitfalls that can afflict more elaborate methods, and (iii) they are simple and straightforward to implement; thus they can be applied almost immediately to many nonlinear optimization problems. These methods do not need to explicitly calculate derivative or gradient information in the parameter space. Typically, these methods maintain a set of points (called the simplex) that is obtained by directly sampling the parameter space. In addition, these methods use a variety of techniques for steep descent (but not necessarily methods of steepest descent) to arrive at near optimal solutions.
Unfortunately, a direct application of the Direct Search method (and its variants) to automatically configure and optimize system parameters in Autonomic Computing systems is likely to fail for a number of reasons. First, Direct Search methods (and its variants) do not work in dynamic environments, where the demand or the load on the system is changing continuously over time, and where the same parameter settings can provide different performance measures at different times. Direct Search methods were designed for static problems and have no built-in mechanism to handle dynamic environments.
Second, Direct Search methods work only for deterministic problems where there is no noise either in measurements of the system's performance on in the system's dynamics. Direct Search methods make the fundamental assumption that the same parameter setting is always going to provide the same performance measure. In noisy or stochastic environments, where such an assumption is not valid, Direct Search methods can fail dramatically in finding good solution regions quickly.
Third, Direct Search methods make certain assumptions about the nature of the parameters being optimized. Typically, Direct Search methods (and the variants) are designed to handle problems with either all real-valued parameters or all integer-valued parameters. In most systems, parameters come in both flavors, and it is necessary to configure and tune both types of parameters simultaneously. In such scenarios, existing Direct Search methods, and the variants, can fail spectacularly since they fail to take the differences in the underlying granularity of the parameter space into account.
Fourth, Direct Search methods, and the variants, cannot handle relational constraints between the parameters being optimized. In many problems of system configuration and optimization, there exist constraints that involve one or more parameters. For example, a set of constraints could indicate that:x1+x2+x3=1.0  constraint #1.0<x1<=1.0  constraint #2.0<=x2 <=1.0  constraint #3.0<=x3 <=1.0  constraint #4where x1, x2, x3 are the system configuration parameters. Direct Search methods, and the variants, were designed for unconstrained problems and are highly inefficient in finding good parameter settings in constrained optimization problems. Thus they have not been employed in online constrained optimization problems.
Finally, Direct Search methods, and the variants, suffer from a number of pathological failure modes that prevent their direct application in many types of optimization problems. For example, in problems with real-valued parameters, the size of the simplex can become infinitesimally small; limiting the Direct Search method's ability to track changes in the optimal parameter settings in dynamic environments. On the other hand, in problems with discrete or integer values, the simplex can easily get stuck in a rut where the Direct Search method is unable to decide on a new point to sample. This pathological failure mode limits Direct Search method's ability to explore promising regions in parameter space.
Therefore, it would be beneficial to have an improved system and method for performing dynamic online multi-parameter optimization for autonomic computing systems that does not suffer from the drawbacks of the Direct Search methods discussed above.